package LeetCode_everyDay;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 655. 输出二叉树
 * 给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。
 *
 *  思路：肯定要使用bfs的思想，
 *       首先是求树的高度； DFS
 *       然后递归遍历创建二叉树。
 */
public class LeetCode655 {
    public List<List<String>> printTree(TreeNode root) {
        // 获取树的高度
        int height = getHeight(root);
        String[][] ans = new String[height][(1<<height)-1];
        for (String[] arr : ans){
            Arrays.fill(arr,"");
        }
        List<List<String>> res = new ArrayList<>();
        fill(ans,root,0,0,ans[0].length);
        for (String[] arr : ans){
            res.add(Arrays.asList(arr));
        }
        return res;
    }

    /**
     * 填充数组
     * @param ans   数组
     * @param root  根节点
     * @param i 第几行
     * @param l 左节点
     * @param r 右节点
     */
    private void fill(String[][] ans,TreeNode root,int i,int l,int r){
        if(root == null){
            return;
        }
        ans[i][(l+r)/2] = ""+root.val;
        fill(ans,root.left,i+1,l,(l+r)/2);
        fill(ans,root.right,i+1,(l+r+1)/2,r);
    }

    /**
     * @param treeNode  获取二叉树的最大高度
     * @return
     */
    private int getHeight(TreeNode treeNode){
        if(treeNode == null){
            return 0;
        }
        return Math.max(getHeight(treeNode.left),getHeight(treeNode.right))+1;
    }

     public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
